package com.peng.leetcode.sort;

/**
 * SortList
 *
 * @author: lupeng6
 * @create: 2020/12/10 20:23
 */
public class SortList {

    public static void main(String[] args) {
        ListNode head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
        ListNode ret = new Solution().sortList(head);
        while (ret != null) {
            System.out.println(ret.val);
            ret = ret.next;
        }
    }


    static class Solution {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }

            // 快慢指针找到中间节点
            ListNode slow = head, fast = head.next;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }

            // 将链表切分成两端
            ListNode temp = slow.next;
            slow.next = null;

            ListNode left = sortList(head);
            ListNode right = sortList(temp);

            //合并两个链表
            return merge(left, right);
        }

        private ListNode merge(ListNode left, ListNode right) {
            ListNode temp = new ListNode(0);
            ListNode index = temp;
            while (left != null && right != null) {
                if (left.val < right.val) {
                    temp.next = left;
                    left = left.next;
                } else {
                    temp.next = right;
                    right = right.next;
                }
                temp = temp.next;
            }
            temp.next = left == null ? right : left;
            return index.next;
        }
    }
}


class ListNode {
    int val;
    ListNode next;

    @Override
    public String toString() {
        return val + "";
    }

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
